package com.company.algo.niuke;

/**
 * 【做过又忘了】
 * 这个二分查找最好在主函数中完成，否则会显得逻辑异常混乱
 */
public class FindK_Largest {
    //快速排序，找到第k大的pivot时返回即可
    public int findKth(int[] a, int n, int K) {
        int l = 0, r = n -1, target = n - K;    //注意：求的是第k【大】,也就是第n-k大的元素
        //二分查找
        while (l<r){
            int mid = quickSelect(a,l,r);
            if (mid == target) return a[mid];
            if (mid < target) l = mid + 1;
            else r = mid -1;
        }
        return a[l];
    }

    private int quickSelect(int[] a, int left, int right){
        int i = left, j = right;
        while(i<j){
            while(i<j && a[j]>=a[left]) j--;
            while(i<j && a[i]<=a[left]) i++;
            if(i!=j) swap(a,i,j);
        }
        swap(a,i,left);
        return j;
    }

    private void swap(int[] input, int i, int j) {
        int tmp = input[i];
        input[i] = input[j];
        input[j] = tmp;
    }

    public int findKth2(int[] a, int n, int K) {
        // write code here
        return quickSelect(a,K,0,n-1);
    }
    private int quickSelect(int[] a, int k, int left, int right){
        if(left>right) return -1;
        int i = left, j = right;
        while(i<j){
            while(i<j && a[j]>=a[left]) j--;
            while(i<j && a[i]<=a[left]) i++;
            if(i!=j) swap(a,i,j);
        }
        swap(a,i,left);
        if(i == a.length-k) return a[i];
        int res = -1;
        if(i > a.length-k) {
            res = quickSelect(a,k,left,i-1);
        } else res = quickSelect(a,k,i+1,right);
        return res;
    }

    public static void main(String[] args) {
        FindK_Largest Main = new FindK_Largest();
        int[] a = {1,3,5,2,2};
        System.out.println(Main.findKth2(a, 5, 1));
    }
}
